//==================================================================
//  Copyright (C) 2006-2007  Davide Pasca
//
//  This library is free software; you can redistribute it and/or
//  modify it under the terms of the GNU Lesser General Public
//  License as published by the Free Software Foundation; either
//  version 2.1 of the License, or (at your option) any later version.
//
//  This library is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
//  Lesser General Public License for more details.
//
//  You should have received a copy of the GNU Lesser General Public
//  License along with this library; if not, write to the Free Software
//  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
//==================================================================
//= Creation: Davide Pasca 2006
//=
//= Based on Mark R. Nelson source from Dr.Dobb's
//=
//==================================================================

#include "psys.h"
#include "memfile.h"
#include "lzw_packer.h"

//==================================================================
using namespace PUtils;

//==================================================================
///
//==================================================================
bool LZW_PackCompress( Memfile *input, Memfile *output )
{
	LZWPacker	packer;

	packer.Reset( output );
	
	if NOT( packer.PackData( input ) )
		return false;
	
	if NOT( packer.EndData() )
		return false;

	return true;
}

//==================================================================
///
//==================================================================
LZWUnpacker::LZWUnpacker( PUtils::Memfile *input )
{
	Reset( input );
}

//==================================================================
void LZWUnpacker::Reset( PUtils::Memfile *input )
{
	_input = input;
	_next_code = 256;			// This is the next available code to define
	_counter = 0;				// Counter is used as a pacifier.
	_string = NULL;
	_completed = true;
}

//==================================================================
u_int LZWUnpacker::unpackInputCode( Memfile *input )
{
	u_int code = input->ReadBits( LZW_BITS );
	return code;
}

//==================================================================
/*
** This routine simply decodes a string from the string table, storing
** it in a buffer.  The buffer can then be output in reverse order by
** the expansion program.
*/
const u_char *LZWUnpacker::unpackDecodeString( u_char *buffer, u_int code )
{
	int i = 0;
	while (code > 255)
	{
		*buffer++ = _append_character[code];
		code = _prefix_code[code];
		if ( i++ >= 4094 )	// based on 12 bits ?
		{
			PASSERT( 0 );
		}
	}

	*buffer = code;

	return buffer;
}

//============================================================================
bool LZWUnpacker::UnpackData( PUtils::Memfile *output, u_int max_out_bytes )
{
	if ( max_out_bytes == 0 )
		return true;

	if NOT( _completed )
	{
		_completed = true;
		goto continue_unpack;
	}

	if ( _input->IsEOF() )
		return false;

	try {
		_old_code = unpackInputCode( _input );	// Read in the first code, initialize the
	} catch (...) {
		return false;
	}

	if ( _old_code == LZW_MAX_VALUE )
		return true;

	_character = _old_code;					// character variable, and send the first

	output->WriteUChar( _old_code );	// code to the output file
	if ( --max_out_bytes == 0 )
		return true;

	//  This is the main expansion loop.  It reads in characters from the LZW file
	//  until it sees the special code used to indicate the end of the data.
	while ( 1 )
	{
		try {
			_new_code = unpackInputCode( _input );
		} catch (...) {
			return false;
		}

		if ( _new_code == LZW_MAX_VALUE )
			break;

		// This code checks for the special STRING+CHARACTER+STRING+CHARACTER+STRING
		// case which generates an undefined code.  It handles it by decoding
		// the last code, and adding a single character to the end of the decode string.
		if ( _new_code >= _next_code )
		{
			*_decode_stack = _character;
			_string = unpackDecodeString( _decode_stack+1, _old_code );
		}
		else // Otherwise we do a straight decode of the new code.
			_string = unpackDecodeString( _decode_stack, _new_code );

		// Now we output the decoded string in reverse order.
		_character = *_string;

continue_unpack:
		while ( _string >= _decode_stack )
		{
			if ( max_out_bytes == 0 )
			{
				_completed = false;
				return true;
			}

			output->WriteUChar( *_string-- );
			--max_out_bytes;
		}

		// Finally, if possible, add a new code to the string table.
		if ( _next_code <= LZW_MAX_CODE )
		{
			_prefix_code[_next_code] = _old_code;
			_append_character[_next_code] = _character;
			_next_code++;
		}

		_old_code = _new_code;
	}

	return true;
}

//============================================================================
bool LZWUnpacker::SeekEnd()
{
	if ( _old_code == LZW_MAX_VALUE )
	{
		_completed = true;
		return true;
	}

	while NOT( _input->IsEOF() )
	{
		_old_code = unpackInputCode( _input );
		if ( _old_code == LZW_MAX_VALUE )
		{
			_completed = true;
			return true;
		}
	}

	return false;
}

//============================================================================
/*
**  This is the expansion routine.  It takes an LZW format file, and expands
**  it to an output file.  The code here should be a fairly close match to
**  the algorithm in the accompanying article.
*/
bool LZW_UnpackExpand( Memfile *input, Memfile *output )
{
	LZWUnpacker	unpack( input );
/*
	do {
		if NOT( unpack.UnpackData( output, 128/*0xffffffff* / ) )
			return false;
	} while NOT( unpack.IsCompleted() );
*/

	if NOT( unpack.UnpackData( output, 0xffffffff ) )
		return false;

	return true;
}

//==================================================================
///
//==================================================================
LZWPacker::LZWPacker( PUtils::Memfile *output )
{
	Reset( output );
}

//==================================================================
void LZWPacker::Reset( PUtils::Memfile *output )
{
	_output = output;

	_next_code = 256;						// Next code is the next available string code
	for (int i=0; i < LZW_TABLE_SIZE; ++i)	// Clear out the string table before starting
		_pack_code_value[i] = -1;

	_is_beginnig = true;
}

//============================================================================
void LZWPacker::packOutputCode( u_int code )
{
	_output->WriteBits( code, LZW_BITS );
}

//============================================================================
/*
** This is the hashing routine.  It tries to find a match for the prefix+char
** string in the string table.  If it finds it, the index is returned.  If
** the string is not found, the first available index in the string table is
** returned instead.
*/
u_int LZWPacker::packFindMatch( int hash_prefix, u_int hash_character )
{
	int index;
	int offset;

	index = (hash_character << LZW_HASHING_SHIFT) ^ hash_prefix;
	if (index == 0)
		offset = 1;
	else
		offset = LZW_TABLE_SIZE - index;

	while (1)
	{
		if (_pack_code_value[index] == -1)
			return(index);

		if (_prefix_code[index] == hash_prefix && _append_character[index] == hash_character)
			return(index);

		index -= offset;

		if (index < 0)
			index += LZW_TABLE_SIZE;
	}
}

//==================================================================
bool LZWPacker::PackData( PUtils::Memfile *input )
{
	if ( _is_beginnig )
	{
		_is_beginnig = false;

		// silently return success if the input file is finished (or maybe empty !)
		if ( input->IsEOF() )
		{
			/*
			try {
			packOutputCode( LZW_MAX_VALUE );		// Output the end of buffer code
			//		pack_output_code( output, 0);				// This code flushes the output buffer
			} catch (...) {
			return false;
			}
			*/

			return true;
		}

		_string_code = input->ReadUChar();	// Get the first code
	}

	/*
	** This is the main loop where it all happens.  This loop runs until all of
	** the input has been exhausted.  Note that it stops adding codes to the
	** table after all of the possible codes have been defined.
	*/
	while ( !input->IsEOF() )
	{
		try {
			u_int character = input->ReadUChar();

			u_int index = packFindMatch( _string_code, character );	// See if the string is in the table.

			if (_pack_code_value[index] != -1)					// If it is,
				_string_code = _pack_code_value[index];			/* get the code value.  If */
			else												/* the string is not in the*/
			{													/* table, try to add it.   */
				if ( _next_code <= LZW_MAX_CODE )
				{
					_pack_code_value[index]		= _next_code++;
					_prefix_code[index]			= _string_code;
					_append_character[index]	= character;
				}

				packOutputCode( _string_code );	// When a string is found  that is not in the table
				_string_code = character;					// I output the last string after adding the new one
			}

		} catch (...) {
			return false;
		}
	}													

	return true;
}

//==================================================================
bool LZWPacker::EndData()
{
	try {
		packOutputCode( _string_code );			// Output the last code
		packOutputCode( LZW_MAX_VALUE );		// Output the end of buffer code
		//	pack_output_code( output, 0);		// This code flushes the output buffer

	} catch (...) {
		//Reset();
		return false;
	}

	//Reset();
	return true;
}